import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}


//官方题解
class Solution {
    int[] rows = new int[9];
    int[] cols = new int[9];
    int[][] blocks = new int[3][3];
    List<int[]> spaces = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        init(board);
        dfs(board, 0);
    }

    void init(char[][] board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                int digit = parseDigit(board[i][j]);
                if(digit == 0){
                    spaces.add(new int[]{i, j});
                }
                else {
                    setPos(i, j, digit, 1);
                }
            }
        }
    }

    boolean dfs(char[][] board, int pos){
        if(pos == spaces.size()){
            return true;
        }

        int i = spaces.get(pos)[0], j = spaces.get(pos)[1];
        int mask = ~(rows[i] | cols[j] | blocks[i / 3][j / 3]) & 0x1FF;  //该位置能填的数字mask
        while(mask != 0){
            int nextDigit = getFirstDigit(mask);
            setPos(i, j, nextDigit, 1);
            board[i][j] = parseChar(nextDigit);
            boolean ret = dfs(board, pos + 1);
            if(ret){
                return true;
            }
            setPos(i, j, nextDigit, 0);
            mask = mask - (1 << (nextDigit - 1));
        }
        return false;
    }

    int getFirstDigit(int mask){
        return Integer.bitCount((mask & (-mask)) - 1) + 1;
    }

    void setPos(int row, int col, int digit, int value){
        if(value == 1){
            rows[row] |= 1 << (digit - 1);
            cols[col] |= 1 << (digit - 1);
            blocks[row / 3][col / 3] |= 1 << (digit - 1);
        }
        else{
            rows[row] &= ~(1 << (digit - 1));
            cols[col] &= ~(1 << (digit - 1));
            blocks[row / 3][col / 3] &= ~(1 << (digit - 1));
        }
    }

    int parseDigit(char c){
        if(c == '.'){
            return 0;
        }
        return c - '0';
    }

    char parseChar(int digit){
        if(digit == 0){
            return '.';
        }
        return (char)(digit + '0');
    }
}

//第二次做
class Solution1 {
    int[] rows = new int[9];
    int[] cols = new int[9];
    int[][] blocks = new int[3][3];
    List<int[]> spaces = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        init(board);
        backtracking(board, 0);
    }

    boolean backtracking(char[][] board, int i) {
        if (spaces.size() == i) {
            return true;
        }
        int n = board.length;
        int row = spaces.get(i)[0], col = spaces.get(i)[1];
        int validChoices = ~(rows[row] | cols[col] | blocks[row / 3][col / 3]) & ((1 << n) - 1);
        while (validChoices != 0) {
            int pos = validChoices & (-validChoices);
            int val = Integer.bitCount(pos - 1) + 1;
            set(val, row, col);
            board[row][col] = (char) (val + '0');
            boolean flag = backtracking(board, i + 1);
            if (flag) {
                return true;
            }
            unset(val, row, col);
            validChoices &= validChoices - 1;
        }
        return false;
    }

    void init(char[][] board) {
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board.length; col++) {
                int v = value(board[row][col]);
                if (v > 0) {
                    set(v, row, col);
                } else {
                    spaces.add(new int[]{row, col});
                }
            }
        }
    }

    void set(int v, int row, int col) {
        rows[row] |= 1 << (v - 1);
        cols[col] |= 1 << (v - 1);
        blocks[row / 3][col / 3] |= 1 << (v - 1);
    }

    void unset(int v, int row, int col) {
        rows[row] &= ~(1 << (v - 1));
        cols[col] &= ~(1 << (v - 1));
        blocks[row / 3][col / 3] &= ~(1 << (v - 1));
    }

    int value(char d) {
        if (d == '.') {
            return 0;
        }
        return d - '0';
    }
}